package leetcode.hot100;

import java.util.ArrayList;
import java.util.List;

/**
 * leetcode-hot100: 矩阵置零
 * 测试链接: https://leetcode.cn/problems/set-matrix-zeroes/?envType=study-plan-v2&envId=top-100-liked
 */
public class SetMatrixZeroes {

    /**
     * 方法一：使用额外空间
     * @param matrix
     */
    public void setZeroes1(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        // 使用额外空间 O(mn)
        List<int[]> records = new ArrayList();
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(matrix[i][j] == 0){
                    records.add(new int[]{i, j});
                }
            }
        }
        for(int[] record : records){
            int x = record[0];
            int y = record[1];
            for(int j = 0; j < n; j++){
                matrix[x][j] = 0;
            }
            for(int i = 0; i < m; i++){
                matrix[i][y] = 0;
            }
        }
    }

    /**
     * 方法二：空间复杂度 O(1)
     * @param matrix
     */
    public void setZeroes2(int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        boolean row0_flag = false;
        boolean col0_flag = false;
        // 第一行是否有零
        for (int j = 0; j < col; j++) {
            if (matrix[0][j] == 0) {
                row0_flag = true;
                break;
            }
        }
        // 第一列是否有零
        for (int i = 0; i < row; i++) {
            if (matrix[i][0] == 0) {
                col0_flag = true;
                break;
            }
        }
        // 把第一行第一列作为标志位
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        // 置0
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (row0_flag) {
            for (int j = 0; j < col; j++) {
                matrix[0][j] = 0;
            }
        }
        if (col0_flag) {
            for (int i = 0; i < row; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}
